// Buffer cache.
//
// The buffer cache is a linked list of buf structures holding
// cached copies of disk block contents.  Caching disk blocks
// in memory reduces the number of disk reads and also provides
// a synchronization point for disk blocks used by multiple processes.
//
// Interface:
// * To get a buffer for a particular disk block, call bread.
// * After changing buffer data, call bwrite to write it to disk.
// * When done with the buffer, call brelse.
// * Do not use the buffer after calling brelse.
// * Only one process at a time can use a buffer,
//     so do not keep them longer than necessary.


#include "types.h"
#include "param.h"
#include "spinlock.h"
#include "sleeplock.h"
#include "riscv.h"
#include "defs.h"
#include "fs.h"
#include "buf.h"

#define NBUCKET 13

struct bucket {
  struct spinlock lock;
  struct buf head;
};

struct {
  struct spinlock lock;
  struct buf buf[NBUF];
  struct bucket bucket[NBUCKET];
} bcache;

void
binit(void)
{
  struct buf *b;

  initlock(&bcache.lock, "bcache");

  for(int i = 0; i < NBUCKET; i++){
    initlock(&bcache.bucket[i].lock, "bcache.bucket");
    bcache.bucket[i].head.prev = &bcache.bucket[i].head;
    bcache.bucket[i].head.next = &bcache.bucket[i].head;
  }

  for(b = bcache.buf; b < bcache.buf+NBUF; b++){
    initsleeplock(&b->lock, "buffer");
    b->refcnt = 0;
    b->timestamp = 0;
  }
}

// Look through buffer cache for block on device dev.
// If not found, allocate a buffer.
// In either case, return locked buffer.
static struct buf*
bget(uint dev, uint blockno)
{
  int hash = blockno % NBUCKET;
  struct bucket *bkt = &bcache.bucket[hash];

  acquire(&bkt->lock);

  // Is the block already cached?
  struct buf *b;
  for(b = bkt->head.next; b != &bkt->head; b = b->next){
    if(b->dev == dev && b->blockno == blockno){
      b->refcnt++;
      release(&bkt->lock);
      acquiresleep(&b->lock);
      return b;
    }
  }

  // Not cached; recycle an unused buffer.
  release(&bkt->lock);

  acquire(&bcache.lock);

  // Find the least recently used buffer with refcnt == 0
  struct buf *victim = 0;
  uint min_ts = ~0U;
  for(int i = 0; i < NBUF; i++){
    b = &bcache.buf[i];
    if(b->refcnt == 0 && b->timestamp < min_ts){
      min_ts = b->timestamp;
      victim = b;
    }
  }
  if(!victim)
    panic("bget: no buffers");

  // If victim is in a different bucket, move it
  int old_hash = victim->blockno % NBUCKET;
  if(victim->valid && old_hash != hash){
    struct bucket *old_bkt = &bcache.bucket[old_hash];
    // Acquire locks in order to avoid deadlock
    if(old_hash < hash){
      acquire(&old_bkt->lock);
      acquire(&bkt->lock);
    } else {
      acquire(&bkt->lock);
      acquire(&old_bkt->lock);
    }
    // Remove from old bucket
    victim->prev->next = victim->next;
    victim->next->prev = victim->prev;
    // Add to new bucket
    victim->next = bkt->head.next;
    victim->prev = &bkt->head;
    bkt->head.next->prev = victim;
    bkt->head.next = victim;
    release(&old_bkt->lock);
    release(&bkt->lock);
  } else if(!victim->valid){
    // Add to bucket
    acquire(&bkt->lock);
    victim->next = bkt->head.next;
    victim->prev = &bkt->head;
    bkt->head.next->prev = victim;
    bkt->head.next = victim;
    release(&bkt->lock);
  }

  victim->dev = dev;
  victim->blockno = blockno;
  victim->valid = 0;
  victim->refcnt = 1;
  victim->timestamp = ticks;

  release(&bcache.lock);

  acquiresleep(&victim->lock);
  return victim;
}

// Return a locked buf with the contents of the indicated block.
struct buf*
bread(uint dev, uint blockno)
{
  struct buf *b;

  b = bget(dev, blockno);
  if(!b->valid) {
    virtio_disk_rw(b->dev, b, 0);
    b->valid = 1;
  }
  return b;
}

// Write b's contents to disk.  Must be locked.
void
bwrite(struct buf *b)
{
  if(!holdingsleep(&b->lock))
    panic("bwrite");
  virtio_disk_rw(b->dev, b, 1);
}

// Release a locked buffer.
// Move to the head of the MRU list.
void
brelse(struct buf *b)
{
  if(!holdingsleep(&b->lock))
    panic("brelse");

  releasesleep(&b->lock);

  b->timestamp = ticks;
  b->refcnt--;
}

void
bpin(struct buf *b) {
  acquire(&bcache.lock);
  b->refcnt++;
  release(&bcache.lock);
}

void
bunpin(struct buf *b) {
  acquire(&bcache.lock);
  b->refcnt--;
  release(&bcache.lock);
}


